Given a dividend X and a divisor N, the remainder of X divided by N is denoted as X mod N. The remainder may also be referred to as a residue.
Modulo arithmetic is used in many applications including number theory, group theory, ring theory, knot theory, abstract algebra, cryptography, computer science, chemistry and the visual and musical arts. Modulo arithmetic may be realized through recursive subtraction which may result in decreased processing throughput. A flow diagram of the conventional recursive subtraction method for modulo arithmetic computation is shown is FIG. 1.
To compute the residue of a division through recursive subtraction method for conditions where the difference between the divisor and the dividend is high, the number of iterations of subtraction is also high. The processing time for the recursive subtraction method varies as a function of the relationship between the input operands.
To perform any arithmetic operations on a continuous sequence of numbers, initial delay to get the results, known as latency, may also be critical. Furthermore, if the processing time for modulo computation of each input number varies, then additional control logic may be required and the throughput may be limited by the worst case scenario.